# Cantor-Bernstein theorem.
Let $A$ and $B$ be two sets. If there exists an injection $f :A \to B$, and an injection $g : B\to A$, then there exists a bijection between $A$ and $B$.
$\blacktriangleright$ Since there is an injection $f : A \to B$, we can assume $A$ is a subset of $B$ without loss, by identifying the elements of $A$ as $f(A)$ in $B$, and $f$ the inclusion map.
So now the claim becomes, if there is a injection $g:B \to A$, where $A$ is a subset of $B$, then there is a bijection between $A$ and $B$.
Let us call the set $B \setminus A$ the *outsider*. Consider $g(B\setminus A)$, the children of the outsiders, and $g^{(2)}(B\setminus A)$, the children of the children of the outsiders, and in general $g^{(k)}(B\setminus A)$ some descendant of the outsiders.
Note that each generation of the outsiders are disjoint and are subsets of $A$. Indeed, if $g^{(m)}(x) = g^{(n)}(y)$ for some $x,y \in B \setminus A$, some $m < n$, then $x = g^{(n-m)}(y) \in A$, a contradiction.
So we have this picture of sets mapped injectively from one to the next $$
B \setminus A \xrightarrow{g} g(B\setminus A) \xrightarrow{g} g^{(2)}(B \setminus A) \xrightarrow{g} g^{(3)}(B\setminus A) \xrightarrow{g} \cdots
$$
Now we define a map $h : B \to A$ where $h(x) = g(x)$ if $x$ is an outsider or some eventual descendant of an outsider, and $h(x) = x$ otherwise.
Note $h$ is injective.
Note $h$ is surjective as we can just find an ancestor, or itself. $\blacksquare$
Let us write $A \sim B$ if there is a bijection between the sets $A$ and $B$. Let us also write $A \preccurlyeq B$ if there is an injection from $A$ to $B$. So Cantor-Bernstein states $A \preccurlyeq B$ and $B \preccurlyeq A$ imply $A \sim B$. We also say $A$ and $B$ are *equinumerous* if $A \sim B$.